<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
单向链表
基本方法有：
1. 追加元素
2. 在指定所引处插入元素
3. 删除指定索引的元素
4. 删除指定元素
5. 根据索引查找指定元素
6. 根据元素查找所在索引
7. 链表长度
8. 是否为空
9. 返回链表头
10. 返回链表尾
<script>
  {
    class Node {
      constructor (options) {
        this.val = options
        this.next = null
      }
    }

    class LinkList {
      #len = 0
      #head = null

      // 追加元素
      push (val) {
        const node = new Node(val)
        if (this.#head) {
          let current = this.#head
          while (current.next) {
            current = current.next
          }
          current.next = node
        } else {
          this.#head = node
        }
        this.#len ++
      }
      // 在指定索引处插入元素
      insert (val, index) {
        if (index >=0 && index <= this.#len) {
          const node = new Node(val)
          if (index === 0) {
            node.next = this.#head
            this.#head = node
          } else {
            const preNode = this.getItemByIndex(index - 1)
            const current = preNode.next
            preNode.next = node
            node.next = current
          }
          this.#len++
        }
      }
      // 删除指定索引的元素
      removeAt (index) {
        if (this.isEmpty()) return
        if (index >= 0 && index < this.#len) {
          let current
          if (index === 0) {
            current = this.#head
            this.#head = this.#head.next
          } else {
            const prevNode = this.getItemByIndex(index - 1)
            current = prevNode.next
            prevNode.next = current.next
          }
          this.#len --
          return current
        }
      }
      // 删除指定元素
      remove (val) {
        let index = this.getIndex(val)
        while (index !== -1) {
          this.removeAt(index)
          index = this.getIndex(val)
        }
      }
      // 根据索引查找指定元素
      getItemByIndex (index) {
        if (index >= 0 && index < this.#len) {
          let i = 0
          let current = this.#head
          while (i < index) {
            current = current.next
            i ++
          }
          return current
        }
      }
      // 比较元素是否相等
      _isEqual (a, b) {
        return a === b
      }
      // 根据元素查找所在索引
      getIndex (val) {
        let current = this.#head
        for (let i = 0; i < this.#len; i ++) {
          if (!current) return -1
          if (this._isEqual(current.val, val)) {
            return i
          }
          current = current.next
        }
        return -1
      }
      // 链表长度
      size () {
        return this.#len
      }
      // 是否为空
      isEmpty () {
        return this.size() === 0
      }
      // 返回链表头
      head () {
        return this.#head
      }
      // 返回链表尾
      tail () {
        return this.getItemByIndex(this.#len - 1)
      }
    }

    const linkList = new LinkList()
    linkList.push('a')
    linkList.push('b')
    linkList.push('c')
    linkList.push('c')
    linkList.push('d')
    linkList.remove('a')
    console.log(linkList)
  }
</script>
双向链表

循环链表



<script>
  /* 单向链表 */
  class Node {
    constructor(element) {
      this.element = element
      this.next = null
    }
  }

  class LinkList {
    #count = 0 // 链表的长度
    #head = null // 链表的头

    push (val) {
      const node = new Node(val)

      if (this.#head) {
        let current = this.#head
        while (current.next) {
          current = current.next
        }
        current.next = node
      } else {
        this.#head = node
      }

      this.#count ++
    }

    getByIndex (index) {
      if (index >=0 && index < this.#count) {
        let current = this.#head
        while (index > 0) {
          current = current.next
          index --
        }
        return current
      }
    }

    removeAt (index) {
      if (index >= 0 && index < this.#count) {
        let current
        if (index === 0) {
          current = this.#head
          this.#head = this.#head.next
        } else {
          let prev = this.getByIndex(index - 1)
          current = prev.next

          prev.next = current.next
        }

        this.#count --

        return current
      }
    }

    getIndex (val) {
      let current = this.#head
      for (let i = 0; i < this.#count; i ++) {
        if (this.isEqual(current.element, val)) {
          return i
        }
        current = current.next
      }
      return -1
    }

    remove (val) {
      let index
      while (index !== -1) {
        index = this.getIndex(val)
        this.removeAt(index)
      }
    }

    isEqual (val1, val2) {
      // todo
      return val1 === val2
    }

    insert (val, index) {
      if (index >=0 && index <= this.#count) {
        const node = new Node(val)
        if (index === 0) {
          node.next = this.#head
          this.#head = node
        } else {
          const prev = this.getByIndex(index - 1)
          const current = prev.next
          prev.next = node
          node.next = current
        }

        this.#count ++
      }
    }

    size () {
      return this.#count
    }

    isEmpty () {
      return this.#count === 0
    }

    getHead () {
      return this.#head
    }
  }

  const linkList = new LinkList()
</script>

<script>
  /* 双向链表 */
  class DoublyNode {
    constructor(element) {
      this.element = element

      this.next = null
      this.prev = null
    }
  }

  class DoublyLinkList {
    #count = 0 // 链表长度
    #head = null // 表头
    #tail = null // 表尾

    push (val) {
      const node = new DoublyNode(val)

      if (this.#count === 0) {
        this.#head = node
        this.#tail = node
      } else {
        this.#tail.next = node
        node.prev = this.#tail

        this.#tail = node
      }

      this.#count ++
    }

    removeAt (index) {
      if (index >= 0 && index < this.#count) {
        let current
        if (index === 0) {
          if (this.#count === 1) {
            current = this.#head
            this.#head = null
            this.#tail = null
          } else {
            current = this.#head
            const nextNode = current.next

            current.next = null
            nextNode.prev = null

            this.#head = nextNode
          }
        } else if (index === this.#count - 1) {
          current = this.#tail
          const prevNode = current.prev

          current.prev = null
          prevNode.next = null

          this.#tail = prevNode
        } else {
          current = this.getByIndex(index)
          const prevNode = current.prev
          const nextNode = current.next

          current.prev = null
          current.next = null

          prevNode.next = nextNode
          nextNode.prev = prevNode
        }

        this.#count --

        return current
      }
    }

    remove (val) {
      let index
      while (index !== -1) {
        index = this.getIndex(val)
        this.removeAt(index)
      }
    }

    insert (val, index) {
      if (index >= 0 && index <= this.#count) {
        const node = new DoublyNode(val)

        if (index === 0) {
          if (this.#count === 0) {
            this.#head = node
            this.#tail = node
          } else {
            node.next = this.#head
            this.#head.prev = node

            this.#head = node
          }
        } else if (index === this.#count) {
          this.#tail.next = node
          node.prev = this.#tail

          this.#tail = node
        } else {
          const current = this.getByIndex(index)
          const prevNode = current.prev

          node.next = current
          current.prev = node

          prevNode.next = node
          node.prev = prevNode
        }

        this.#count ++

        return true
      }
      return false
    }

    getByIndex (index) {
      if (index >=0 && index < this.#count) {
        let current = this.#head
        while (index > 0) {
          current = current.next
          index --
        }
        return current
      }
    }

    getIndex (val) {
      let current = this.#head
      for (let i = 0; i < this.#count; i ++) {
        if (this.isEqual(current.element, val)) {
          return i
        }
        current = current.next
      }
      return -1
    }

    isEqual (val1, val2) {
      // todo
      return val1 === val2
    }

    size () {
      return this.#count
    }

    isEmpty () {
      return this.#count === 0
    }

    getHead () {
      return this.#head
    }

    getTail () {
      return this.#tail
    }
  }

  const doublyLinkList = new DoublyLinkList()
</script>

<script>
  /* 循环链表 */
  class CircleNode {
    constructor(element) {
      this.element = element
      this.next = null
    }
  }

  class CircleLinkList {
    #count = 0 // 链表长度
    #head = null // 表头

    push (val) {
      const node = new CircleNode(val)

      if (this.#count === 0) {
        this.#head = node
        node.next = this.#head
      } else {
        const tail = this.getByIndex(this.#count - 1)
        tail.next = node
        node.next = this.#head
      }

      this.#count ++
    }

    insert (val, index) {
      if (index >= 0 && index <= this.#count) {
        const node = new CircleNode(val)

        if (index === 0) {
          if (this.#count === 0) {
            this.#head = node
            node.next = this.#head
          } else {
            const tail = this.getByIndex(this.#count - 1)
            node.next = this.#head
            this.#head = node
            tail.next = this.#head
          }
        } else if (index === this.#count) {
          const tail = this.getByIndex(this.#count - 1)
          tail.next = node
          node.next = this.#head
        } else {
          const prevNode = this.getByIndex(index - 1)
          node.next = prevNode.next
          prevNode.next = node
        }

        this.#count ++

        return true
      }

      return false
    }

    removeAt (index) {
      if (index >= 0 && index < this.#count) {
        if (index === 0) {
          if (this.#count === 1) {
            this.#head = null
          } else {
            const tail = this.getByIndex(this.#count - 1)
            this.#head = this.#head.next
            tail.next = this.#head
          }
        } else if (index === this.#count - 1) {
          const prevNode = this.getByIndex(index - 1)
          prevNode.next = this.#head
        } else {
          const prevNode = this.getByIndex(index - 1)
          const current = prevNode.next
          prevNode.next = current.next
        }

        this.#count --
        return true
      }
      return false
    }

    remove (val) {
      let index
      while (index !== -1) {
        index = this.getIndex(val)
        this.removeAt(index)
      }
    }

    isEqual (val1, val2) {
      // todo
      return val1 === val2
    }

    getIndex (val) {
      let current = this.#head
      for (let i = 0; i < this.#count; i ++) {
        if (this.isEqual(current.element, val)) {
          return i
        }
        current = current.next
      }
      return -1
    }

    getByIndex (index) {
      if (index >=0 && index < this.#count) {
        let current = this.#head
        while (index > 0) {
          current = current.next
          index --
        }
        return current
      }
    }

    size () {
      return this.#count
    }

    isEmpty () {
      return this.#count === 0
    }

    getHead () {
      return this.#head
    }
  }

  const circleLinkList = new CircleLinkList()
</script>
</body>
</html>
